package 牛客;

import 剑指offer.ListNode;

public class p链表中倒数第k个结点 {
    public ListNode FindKthToTail(ListNode head, int k) {
        //快慢指针
        //快指针比慢指针 先走 k-1步，再同时走,fast.next==null时，返回slow
        if (head==null) {
            return null;
        }
        if (k==0) {
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;

        for (int i = 0; i <k-1; i++) {
            if (fast.next==null) {
                //当 k值过大，超过节点总个数
                return null;
            }
            fast=fast.next;
        }
        while (fast.next!=null) {
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    public ListNode FindKthToTail1(ListNode head, int k) {
        //遍历两遍的做法,cur走 总个数-k 步
        if (head==null) {
            return null;
        }
        ListNode cur=head;
        int count=0;
        while (cur!=null) {
            count++;
            cur=cur.next;
        }

        if (count<k) {
            return null;
        }

        ListNode res=head;
        for (int i = 0; i <count; i++) {
            res=res.next;
        }
        return res;
    }
}
